M07 Loop Detection, part 2 - IPv4, Routing
Lecture Video
Dynamic Routing
In the last chapter we learned about switching loops in OSI Model Layer 2.
- Frame gets forwarded again and again in a loop
The same phenomenon can happen as routing loops in OSI Model Layer 3.
- Packet gets forwarded again and again in a loop
Our luck in OSI Model Layer 3 is the Time To Live -field which prevents disastrous network meltdowns.
Static routing can easily form a routing loop when configured wrong. This is why automatization of static routes is presented, called dynamic routing.
The difference between Dynamic vs Static
Static routes are easy to understand as they are set by the network administrator. They are basically road signs (this subnet, this distance and this direction) on intersections (routers).
Dynamic routing is a different kind of an animal.
- The routers learn of one another through formed
adjacencies - The
adjacenciesare formed through formal procedure to establish neighborships - And afterwards subnet reachability information is shared
These steps are solved by different, competing protocols.
Solutions
Distance Vector
As the name says, each of the subnets are declared being a certain distance and vector away. E.g.
distance = 100 kilometers
vector = northwest
These distances and vectors are advertised to adjacent routers. So some blame them to be "hear-say" and subject to "Broken Phone" phenomenon.
Protocols in this family are:
- Border Gateway Protocol - BGP - this is the one concentrated on this course
- Routing Information Protocol - RIP
- Enhanced Interior Gateway Routing Protocol - EIGRP
Shortest Path First
This family of dynamic routing protocols follow the same algorithm; Djistra's algorithm - Shortest Path First.
The algorithm requires a complete database (or a view of the topology). The algorithm is then applied to the database to find the shortest path to each subnet. The details of the algorithm is a part of Data Structures and Algorithms -course.
Protocols in this family are:
- Open Shortest Path First - OSPF - this is the one concentrated on this course
- Intermediate System to Intermediate System - IS-IS
OSPF - Open Shortest Path First
OSPF has formed to be the de facto routing protocol in many routed networks.
"OSPF is designed to be run internal to a single Autonomous System. Each OSPF router maintains an identical database describing the Autonomous System's topology. From this database, a routing table is calculated by constructing a shortest-path tree."
Cost (or speed)
At the basis of OSPF is cost of different links. This is the metric which is used to differentiate the shortest path through the network.
Different (ethernet) link speeds are used to calculate this cost based on reference-bandwidth of 100 000 000 or 10^8.
Note
The reference bandwidth is 100 Mbit/s respectively, thus a 100M Ethernet link has a cost of 1
100 000 000 / 100 000 000 = 1
Anyways it can be altered through.
vyos@vyos# set protocols ospf auto-cost reference-bandwidth
Possible completions:
<1-4294967> Reference bandwidth cost in Mbits/sec (default 100)
Warning
This variable can be changed through configuration, but it has to be identical within all the OSPF routers in the network (or Autonomous System). This is warned by Vyos:
[ protocols ospf auto-cost reference-bandwidth 1000 ]
OSPF: Reference bandwidth is changed.
Please ensure reference bandwidth is consistent across all routers
Adjacency
Adjacencies are formed through exchange of OSPF -packets.
| OSPF Packet Type | Meaning |
|---|---|
| Hello | Establishes and upkeeps adjacency information with neighbors |
| Database Description Packet | Describes the contents of OSPF (link-state) database |
| Link State Request | Requests OSPF database rows from a neighboring router |
| Link State Update | Sends link-state advertisements (LSAs) to neighbor routers |
| Link State Acknowledgement | Acknowledges the reception of LSAs to neighbors |
Router-ID in Adjacency
OSPF Routers have to identify themselves with router-id. This is used to pinpoint what router is what. An IPv4 address is used to identify a router.
Typically the choice of router-id is done by
- router-id -command
set protocols ospf parameters router-id <x.x.x.x> - highest binary number/address (remember IPv4 is a 32 bit variable) of loopback interfaces
- highest binary number/address (remember IPv4 is a 32 bit variable) of other interfaces (e.g. ethernet0)
Loopback interface?
Loopback interfaces are interfaces on a router that never go down unless the device is on fire/operating system is crashing.
It makes sense to have an interface that is "always up" as it is good for - network device management ip address - for processes to use such as OSPF, BGP, ...
Typical Ethernet ports might go down because of link failure. Thus if the management is bound to that singular interface eth0, and the link goes down. The whole router "seems to be down" eventhought it might have a completely valid ip address working on interface eth1.
Loopback's do not connect to anywhere, thus /32 subnet mask addresses are used in them. They identify a singular router. The address can be set by:
set interfaces loopback lo address <x.x.x.x/32>
Remember that it is a (really small) subnet of its own, and it has to be dynamically routed same as other subnets.
Neighborship states
Neighborships go through different states based on what kind of information has been exchanged between the adjacent routers.
| Neighborship | Meaning |
|---|---|
| Down | no information is exchanged with anyone |
| Init | OSPF sends Hello packets at regular intervals to find neighboring routers |
| Two-way | OSPF has seen another router's Hello packet! |
| ExStart | The two routers are sending DataBase Description (DBD) packets and electing Designated Router for the ethernet segment |
| Exchange | The two routers are sending DataBase Description (DBD) packets and comparing that both have a complete database |
| Loading | Routers can still send LSAs to one another to ask for more information |
| Full adjacency | Shortest Path First has been ran through the database and a routing table is ready |
OSPF isn't the fastest protocol to go through the states and load the database into a routing table
Be patient! Especially with our virtual machines...
Neighborship packet exchange example
The wireshark can be found here.
1 - OSPF Hello!
2 - OSPF Hello!
3 - OSPF Hello! I see you 192.168.15.254
4 - OSPF Hello! I see you 172.16.0.1
5 - OSPF Hello! I am DR
6 - OSPF Hello! You are DR
7 - OSPF DBD! This is my Database
8 - OSPF DBD! This is my Database
9 - OSPF DBD! LSA1: Here is one link-state
10 - OSPF DBD! LSA1: Here is one link-state
11 - OSPF DBD! Nice! LSRequest: Tell me more
12 - OSPF DBD! Nice! LSUpdate: Here is more
13 - OSPF DBD! Nice! LSAcknowledge: received!
Databases
OSPF Database
This is the one database of the protocol. This is populated by different link-state(s) updated by neighboring routers into one big database of link-states.
This can be investigated from the router with the command show ip ospf database
vyos@vyos:~$ show ip ospf database
OSPF Router with ID (192.168.15.254)
Router Link States (Area 0.0.0.0)
Link ID ADV Router Age Seq# CkSum Link count
172.16.0.1 172.16.0.1 434 0x80000008 0x4837 2
192.168.15.254 192.168.15.254 447 0x8000000a 0x628c 3
Net Link States (Area 0.0.0.0)
Link ID ADV Router Age Seq# CkSum
25.0.0.1 192.168.15.254 427 0x80000005 0xfb93
vyos@vyos:~$
Shortest Path First -algorithm is ran through to form a Shortest Path Tree.
Routing Information Base - RIB
After the Shortest Path Tree has been concluded, the implementation of it is established in the routing table.
vyos@vyos:~$ show ip route
Codes: K - kernel route, C - connected, S - static, R - RIP,
O - OSPF, I - IS-IS, B - BGP, E - EIGRP, N - NHRP,
T - Table, v - VNC, V - VNC-Direct, A - Babel, D - SHARP,
F - PBR, f - OpenFabric,
> - selected route, * - FIB route
O 25.0.0.0/24 [110/100] is directly connected, eth1, 01:40:31
C>* 25.0.0.0/24 is directly connected, eth1, 01:47:15
O>* 172.16.0.0/24 [110/200] via 25.0.0.2, eth1, 01:39:36
O 192.168.0.0/24 [110/1000] is directly connected, eth0.5, 01:40:31
C>* 192.168.0.0/24 is directly connected, eth0.5, 01:47:16
O 192.168.10.0/24 [110/1000] is directly connected, eth0.10, 01:40:31
C>* 192.168.10.0/24 is directly connected, eth0.10, 01:47:15
C>* 192.168.15.0/24 is directly connected, eth0.15, 01:47:15
vyos@vyos:~$
Note! There are separated rows for the same networks, but >* is the selected route and FIB route (installed into the forwarding information base and thus used for forwarding packets).
Areas and roles
Roles
Designated Router - DR
Is a router that primarely handles the distribution of LSAs in a multiaccess network segment (such as Ethernet)
Backup Designated Router - BDR
Is a router that secondarely handles the distribution of LSAs in a multiaccess network segment (such as Ethernet). It takes it role as a primary distributor if the DR disappears from the network segment.
Drother - an OSPF capable router
Listens to the DR and BDR for network updates, and informs its own changes to them. It is the resposibility of DR to send the update from one Drother to other Drothers.
Area Border Router - ABR
As OSPF is segmented to areas, the routers between the areas are declared as Area Border Routers. They have OSPF databases per area, thus multiple databases reside in one ABR.
What is an Area
Area is a singular OSPF database. Distribution of areas results to smaller databases -> faster algorithm runtime. So segmentation of the OSPF routing domain is preferred to result in a faster routing topology.
There is an 'old' recommendation of 50 routers in one Area
Althought performance increases in hardware might have increased the amount.
If the areas are segmented, then changes in one area do not affect another area. Saving database changes, saving algorithm run times.
How areas should be formed
Now this is at the core of the link-state routing algorithm.
Area 0 is the backbone area of OSPF. All other areas must be connected to the backbone area.
Otherwise OSPF changes into Distance-Vector routing protocol
This is definately not what we want
Example picture of Areas/Roles
Configuring OSPF
This chapter has a lot of commands that are summarized (or even repeated) here
Setting Up OSPF
set protocols ospf parameters router-id <x.x.x.x>
If you want the router-id to be assigned manually, use set protocols ospf parameters router-id <x.x.x.x> where <x.x.x.x> is e.g. the loopback IPv4 address.
set protocols ospf area 0 network <x.x.x.x/xx>
Where <x.x.x.x/xx> is the network address of subnets connected to the OSPF router.
The command has dual meaning.
- It sends and receives
OSPF Hellopackets in the interface that has the network configured - It adds the network to the OSPF database and starts to advertise it to neighbors
Commands to add cyber security to OSPF
set protocols ospf passive-interface <interface>
The set protocols ospf area 0 network <x.x.x.x/xx> command starts to send OSPF Hello packets to the given <x.x.x.x/xx> subnet. This might not always be the desired effect as the command statement is required also for advertisement of the subnet. To switch off the OSPF Hello packets one can use the command above. (e.g. to disable OSPF Hello from workstations VLAN)
set protocols ospf area 0 authentication md5
If further security is required, the OSPF neighbors can authenticate themselves using MD5 hash-function algorithm.
The "password" (or the message-digest derived from it) has to be established per interface.
set interfaces ethernet eth0 ip ospf authentication md5 key-id <id> md5-key <MD5 Key (16 characters or less)>
The "password" (or the message-digest derived from it) has to be established per interface.
Example
set interfaces ethernet eth0 ip ospf authentication md5 key-id 1 md5-key kissa123
Info: What is an MD5-key?
"kissa123" results in a (md5) hash of 7b2b0f47573b18442d941b7487a76804 within the OSPF HELLO -messages.
The hash can be verified on student.labranet.jamk.fi if you wish
[sahka@student ~]$ echo kissa123 > md5_passu.txt
[sahka@student ~]$ cat md5_passu.txt
kissa123
[sahka@student ~]$ md5sum md5_passu.txt
7b2b0f47573b18442d941b7487a76804 md5_passu.txt
[sahka@student ~]$
Hash functions are a part of the Cyber Security -course.
Verifying the Functionality of OSPF
The first thing to troubleshoot is the establishment of neighborships. The states can be verified by:
show ip ospf neighbor
vyos@vyos:~$ show ip ospf neighbor
Neighbor ID Pri State Dead Time Address Interface RXmtL RqstL DBsmL
172.16.0.1 1 Full/Backup 32.794s 25.0.0.2 eth1:25.0.0.1 0 0 0
Often skipped as the OSPF database is just a phase before the actual routing table, but still sometimes required for investigation to understand how OSPF is handling the LSAs. Thus you can verify the integrity of the database through the command:
show ip ospf database
vyos@vyos:~$ show ip ospf database
OSPF Router with ID (192.168.15.254)
Router Link States (Area 0.0.0.0)
Link ID ADV Router Age Seq# CkSum Link count
172.16.0.1 172.16.0.1 1125 0x8000000a 0x4439 2
192.168.15.254 192.168.15.254 739 0x80000011 0x4bd5 3
Net Link States (Area 0.0.0.0)
Link ID ADV Router Age Seq# CkSum
25.0.0.1 192.168.15.254 1109 0x80000007 0xf795
Often the end result is the goal. Thus the established routes in the routing table can be investigated by
show ip route
vyos@vyos:~$ show ip route
Codes: K - kernel route, C - connected, S - static, R - RIP,
O - OSPF, I - IS-IS, B - BGP, E - EIGRP, N - NHRP,
T - Table, v - VNC, V - VNC-Direct, A - Babel, D - SHARP,
F - PBR, f - OpenFabric,
> - selected route, * - FIB route
O 25.0.0.0/24 [110/1] is directly connected, eth1, 00:43:25
C>* 25.0.0.0/24 is directly connected, eth1, 02:50:07
O>* 172.16.0.0/24 [110/101] via 25.0.0.2, eth1, 00:43:25
O 192.168.0.0/24 [110/1] is directly connected, eth0.5, 00:41:55
C>* 192.168.0.0/24 is directly connected, eth0.5, 02:50:08
O 192.168.10.0/24 [110/1] is directly connected, eth0.10, 00:41:55
C>* 192.168.10.0/24 is directly connected, eth0.10, 02:50:07
C>* 192.168.15.0/24 is directly connected, eth0.15, 02:50:07
And if only OSPF related routes are investigated, it can filter out the OSPF routes by
show ip route ospf
vyos@vyos:~$ show ip route ospf
Codes: K - kernel route, C - connected, S - static, R - RIP,
O - OSPF, I - IS-IS, B - BGP, E - EIGRP, N - NHRP,
T - Table, v - VNC, V - VNC-Direct, A - Babel, D - SHARP,
F - PBR, f - OpenFabric,
> - selected route, * - FIB route
O 25.0.0.0/24 [110/1] is directly connected, eth1, 00:43:49
O>* 172.16.0.0/24 [110/101] via 25.0.0.2, eth1, 00:43:49
O 192.168.0.0/24 [110/1] is directly connected, eth0.5, 00:42:19
O 192.168.10.0/24 [110/1] is directly connected, eth0.10, 00:42:19
If there are problems with the whole OSPF instance. The settings can be verified by
show ip ospf
vyos@vyos:~$ show ip ospf
OSPF Routing Process, Router ID: 192.168.15.254
Supports only single TOS (TOS0) routes
This implementation conforms to RFC2328
RFC1583Compatibility flag is disabled
OpaqueCapability flag is disabled
Initial SPF scheduling delay 0 millisec(s)
Minimum hold time between consecutive SPFs 50 millisec(s)
Maximum hold time between consecutive SPFs 5000 millisec(s)
Hold time multiplier is currently 1
SPF algorithm last executed 38m50s ago
Last SPF duration 74 usecs
SPF timer is inactive
LSA minimum interval 5000 msecs
LSA minimum arrival 1000 msecs
Write Multiplier set to 20
Refresh timer 10 secs
Number of external LSA 0. Checksum Sum 0x00000000
Number of opaque AS LSA 0. Checksum Sum 0x00000000
Number of areas attached to this router: 1
Area ID: 0.0.0.0 (Backbone)
Number of interfaces in this area: Total: 3, Active: 3
Number of fully adjacent neighbors in this area: 1
Area has no authentication
SPF algorithm executed 7 times
Number of LSA 3
Number of router LSA 2. Checksum Sum 0x0000900e
Number of network LSA 1. Checksum Sum 0x0000f795
Number of summary LSA 0. Checksum Sum 0x00000000
Number of ASBR summary LSA 0. Checksum Sum 0x00000000
Number of NSSA LSA 0. Checksum Sum 0x00000000
Number of opaque link LSA 0. Checksum Sum 0x00000000
Number of opaque area LSA 0. Checksum Sum 0x00000000
If there is some problems with neighborship formation, it is sometimes good to verify that OSPF is actively handling that interface through:
show ip ospf interface
vyos@vyos:~$ show ip ospf interface
eth0.5 is up
ifindex 4, MTU 1500 bytes, BW 100 Mbit <UP,BROADCAST,RUNNING,MULTICAST>
Internet Address 192.168.0.254/24, Broadcast 192.168.0.255, Area 0.0.0.0
MTU mismatch detection: enabled
Router ID 192.168.15.254, Network Type BROADCAST, Cost: 1
Transmit Delay is 1 sec, State DR, Priority 1
No backup designated router on this network
Multicast group memberships: OSPFAllRouters OSPFDesignatedRouters
Timer intervals configured, Hello 10s, Dead 40s, Wait 40s, Retransmit 5
Hello due in 6.874s
Neighbor Count is 0, Adjacent neighbor count is 0
eth0.10 is up
ifindex 6, MTU 1500 bytes, BW 100 Mbit <UP,BROADCAST,RUNNING,MULTICAST>
Internet Address 192.168.10.254/24, Broadcast 192.168.10.255, Area 0.0.0.0
MTU mismatch detection: enabled
Router ID 192.168.15.254, Network Type BROADCAST, Cost: 1
Transmit Delay is 1 sec, State DR, Priority 1
No backup designated router on this network
Multicast group memberships: OSPFAllRouters OSPFDesignatedRouters
Timer intervals configured, Hello 10s, Dead 40s, Wait 40s, Retransmit 5
Hello due in 7.171s
Neighbor Count is 0, Adjacent neighbor count is 0
eth1 is up
ifindex 3, MTU 1500 bytes, BW 1000 Mbit <UP,BROADCAST,RUNNING,MULTICAST>
Internet Address 25.0.0.1/24, Broadcast 25.0.0.255, Area 0.0.0.0
MTU mismatch detection: enabled
Router ID 192.168.15.254, Network Type BROADCAST, Cost: 1
Transmit Delay is 1 sec, State DR, Priority 1
Backup Designated Router (ID) 172.16.0.1, Interface Address 25.0.0.2
Saved Network-LSA sequence number 0x80000007
Multicast group memberships: OSPFAllRouters OSPFDesignatedRouters
Timer intervals configured, Hello 10s, Dead 40s, Wait 40s, Retransmit 5
Hello due in 6.656s
Neighbor Count is 1, Adjacent neighbor count is 1
Continue to the Exercises
Self-reflect the material with a small quiz?
Data Networks Quiz - M07 Loop Detection, part 2 - IPv4, Routing
Back to the Schedule?
License
This course and its materials are written by Karo Saharinen and licenced by Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license.
